import java.util.*;

public class BinaryTree {
    public TreeNode root;
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left= D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        root=A;
        return root;
    }
    public TreeNode createTree1(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left= D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.left=H;
        root=A;
        return root;
    }
    public void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void midOrder(TreeNode root){
        if (root==null){
            return;
        }
        midOrder(root.left);
        System.out.print(root.val+" ");
        midOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if (root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //一棵树的节点个数
    public int size(TreeNode root){
        if (root==null){
            return 0;
        }
        return 1+size(root.left)+size(root.right);
    }
    public static  int sizeNode;
    public void size2(TreeNode root) {
        if (root==null){
            return ;
        }
        sizeNode++;
        size2(root.left);
        size2(root.right);
    }

    //求叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        if (root==null){
          return 0;
        }
       if (root.left==null&&root.right==null){
           return 1;
       }
       return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    public static  int sizeLeafNode;
    public void getLeafNodeCount2(TreeNode root){
        if (root==null){
            return ;
        }
        if (root.left==null&&root.right==null){
           sizeLeafNode++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);

    }

    //获取k层节点的个数
    //前提k是合法的
    public int getKLevelNodeCount(TreeNode root,int k){
       if (root==null ){
           return 0;
       }
       if (k==1){
           return 1;
       }
       return getKLevelNodeCount(root.left,k-1)
               +getKLevelNodeCount(root.right,k-1);
    }

    //获取树的高度(左树和右树的的最大值+1)
    //时间复杂度为O（n）
    public int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
    public TreeNode find(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if (root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if (ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }else {
            return null;
        }
    }

    //检查两棵树是否相同
    /**
     * 时间复杂度：O(min（m,n）)
     * @param p 有m个节点
     * @param q 有n个节点
     */
    public boolean isSameTree(TreeNode p,TreeNode q){
        if (p==null&&q==null){
            return true;
        }
        if (p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if (p.val!= q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

    }

    //第二棵树是否是第一棵树的子树
    /**
     * 时间复杂度：O（m*n）
     * @param root 有n个节点
     * @param subRoot 有m个节点
     */
    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        if (root==null&&subRoot!=null){
            return false;
        }
        if (root.val== subRoot.val){
           return isSameTree(root,subRoot);
        }
        return isSubTree(root.left,subRoot)
                ||isSubTree(root.right,subRoot);
    }
    /*时间复杂度较大
    public boolean isSubTree2(TreeNode root,TreeNode subRoot){
        if (root==null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubTree(root.left,subRoot)){
            return true;
        }
        if (isSubTree(root.right,subRoot)){
            return true;
        }
        return false;
    }*/

    public TreeNode createTree3(){
        TreeNode C=new TreeNode('C');
        //TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        //C.left=F;
        C.right=G;
        root=C;
        return root;
    }

    //翻转二叉树
    private void swap(TreeNode root){
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
    }
    public TreeNode reverseTree(TreeNode root){
        if (root==null||root.left==null&&root.right==null){
            return root;
        }
        swap(root);
        reverseTree(root.left);
        reverseTree(root.right);
        return root;
    }
    //判断一棵二叉树是否是平衡二叉树（所有节点的高度差小于等于一）
    /**
     * 时间复杂度：0（n*n）
     * @param root
     * @return
     */

    public boolean isBalanced(TreeNode root){
        if (root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.abs(leftHeight-rightHeight)<=1
                &&isBalanced(root.left)&&isBalanced(root.right);
    }
    public TreeNode createTree4(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left= D;
        B.right=E;
        C.left=F;
        D.left=H;
        H.right=G;
        root=A;
        return root;
    }
    //优化：
    /**
     * 时间复杂度：0（n）
     * @param root
     * @return
     */
    public int getHeight2(TreeNode root){
       if (root==null){
           return 0;
       }
       int left=getHeight2(root.left);
       if (left<0){
           return -1;
       }
       int right=getHeight2(root.right);
       if (right<0){
           return -1;
       }
       if (Math.abs(left-right)<=1){
           return Math.max(left,right)+1;
       }else {
           return -1;
       }
    }
    public boolean isBalanced2(TreeNode root){
        if (root==null){
            return true;
        }
        return getHeight2(root)>0;

    }

    //对称二叉树
    private boolean isSymmetricChild(TreeNode p,TreeNode q){
        if (p.left==null&&p.right==null&&q.left==null&&q.right==null){
            return true;
        }
        if (p.left!=null&&q.right==null
                ||p.left==null&&q.right!=null
                ||p.right!=null&&q.left==null
                ||p.right==null&&q.left!=null){
            return false;
        }
        if (p.left.val!=q.right.val
                ||p.right.val!=q.left.val){
            return false;
        }
        return isSymmetricChild(p.left,q.right)
                &&isSymmetricChild(p.right,q.left);
    }

    public boolean isSymmetric(TreeNode root){
        if (root==null||root.left==null&&root.right==null){
            return true;
        }
        if (root.left==null&&root.right!=null
                ||root.left!=null&&root.right==null){
            return false;
        }
        if (root.left.val!=root.right.val){
            return false;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public BinaryTree.TreeNode createTree5(){
        BinaryTree.TreeNode A=new BinaryTree.TreeNode('1');
        BinaryTree.TreeNode B=new BinaryTree.TreeNode('2');
        BinaryTree.TreeNode C=new BinaryTree.TreeNode('2');
        BinaryTree.TreeNode D=new BinaryTree.TreeNode('3');
        BinaryTree.TreeNode E=new BinaryTree.TreeNode('4');
        BinaryTree.TreeNode F=new BinaryTree.TreeNode('4');
        BinaryTree.TreeNode G=new BinaryTree.TreeNode('3');
        BinaryTree.TreeNode H=new BinaryTree.TreeNode('5');
        BinaryTree.TreeNode I=new BinaryTree.TreeNode('6');
        BinaryTree.TreeNode J=new BinaryTree.TreeNode('6');
        BinaryTree.TreeNode K=new BinaryTree.TreeNode('5');
        BinaryTree.TreeNode L=new BinaryTree.TreeNode('7');
        A.left=B;
        A.right=C;
        B.left= D;
        B.right=E;
        C.left=F;
        C.right=G;
        D.right=H;
        D.left=I;
        I.left=L;
        G.left=J;
        G.right=K;
        root=A;
        return root;
    }
    //输入前序遍历（标明了空节点的位置）输出中序遍历
    private static int i;
    public TreeNode createTree2(String str){
        TreeNode root=null;
        if (str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree2(str);
            root.right=createTree2(str);
        }else {
            i++;
        }
        return root;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode ret=queue.peek();
            if (ret.left!=null){
                queue.offer(ret.left);
            }
            if (ret.right!=null){
                queue.offer(ret.right);
            }
            System.out.print(queue.poll().val+" ");
        }
        System.out.println();
    }

    public List<List<Character>> levelOrder2(TreeNode root){
        List<List<Character>> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size= queue.size();
            List<Character> list=new LinkedList<>();
            while (size>0){
                TreeNode node=queue.peek();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null) {
                    queue.offer(node.right);
                }
                list.add(queue.poll().val);
                size--;
            }
            ret.add(list);
        }
        return ret;

    }
    //是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root==null){
            return true;
        }
       Queue<TreeNode>queue=new LinkedList<>();
       queue.offer(root);
       while (!queue.isEmpty()){
           TreeNode node=queue.poll();
           if (node==null){
               break;
           }
           queue.offer(node.left);
           queue.offer(node.right);
       }
       while (!queue.isEmpty()){
           if (queue.poll()!=null){
               return false;
           }
       }
       return true;
    }

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return null;
        }
        if (p==root||q==root){
            return root;
        }
        TreeNode ret1=lowestCommonAncestor(root.left,p,q);
        TreeNode ret2=lowestCommonAncestor(root.right,p,q);
        if (ret1!=null&&ret2!=null){
            return root;
        } else if (ret1==null) {
            return ret2;
        }else {
            return ret1;
        }
    }
    //法二：
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if (root==null){
            return false;
        }
        stack.push(root);
        if (root==node){
            return true;
        }
        boolean flag1=getPath(root.left,node,stack);
        if (flag1){
            return true;
        }
        boolean flag2=getPath(root.right,node,stack);
        if (flag2){
            return true;
        }
        stack.pop();
        return false;

    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p,TreeNode q) {
        if (root==null){
            return null;
        }
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int size1= stackP.size();
        int size2= stackQ.size();
        int size;
        if (size1>size2){
            size=size1-size2;
            while (size>0){
                stackP.pop();
                size--;
            }
        }else {
            size=size2-size1;
            while (size>0){
                stackQ.pop();
                size--;
            }
        }
        while (!stackP.isEmpty()&&!stackQ.isEmpty()){
            if (stackP.peek()==stackQ.peek()){
                return stackP.pop();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;
    }

    //前序遍历（非递归）
    public void preOrder2(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        TreeNode cur=stack.pop();
        stack.push(cur.right);
        stack.push(cur.left);
        System.out.print(cur.val+" ");
        while (!stack.isEmpty()){
            cur=stack.pop();
            if (cur.right!=null){
                stack.push(cur.right);
            }
            if (cur.left!=null) {
                stack.push(cur.left);
            }
            System.out.print(cur.val+" ");
        }
    }
    public void preOrder3(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode old=stack.pop();
            cur=old.right;
        }
        System.out.println();
    }
    //中序遍历（非递归）
    public void midOrder2(TreeNode root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode old=stack.pop();
            System.out.print(old.val+" ");
            cur=old.right;
        }
        System.out.println();
    }
    //后序遍历（非递归）
    public void postOrder2(TreeNode root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode old=stack.peek();
            if (old.right==null||prev==old.right){
                stack.pop();
                System.out.print(old.val+" ");
                prev=old;
            }else {
                cur=old.right;

            }
        }
        System.out.println();
    }
    //前序与中序遍历来构造二叉树(难)
    private static int proIndex;
    private int findIndex(char[] midOrder,TreeNode node,int start,int end){
        for (int j = start; j <= end; j++) {
            if (midOrder[j]==node.val){
                return j;
            }
        }
        return -1;
    }
    private TreeNode buildTreePMChild(char[] proOrder,char [] midOrder,int midBegin,int midEnd){
        if (midBegin>midEnd){
            return null;
        }
        TreeNode root=new TreeNode(proOrder[proIndex]);
        int rootIndex=findIndex(midOrder,root,midBegin,midEnd);
        proIndex++;
        root.left=buildTreePMChild(proOrder,midOrder,midBegin,rootIndex-1);
        root.right=buildTreePMChild(proOrder,midOrder,rootIndex+1,midEnd);
        return root;
    }
    public  TreeNode buildTreePM(char[] proOrder,char [] midOrder){
        return buildTreePMChild(proOrder,midOrder,0,midOrder.length-1);

    }

    //根据中序和后序进行创建一个二叉树
    private static int postIndex;
    private TreeNode buildTreeMPChild(char[] midOrder,char [] postOrder,int midBegin,int midEnd){
        if (midBegin>midEnd){
            return null;
        }
        TreeNode root=new TreeNode(postOrder[postIndex]);
        int midIndex=findIndex(midOrder,root,midBegin,midEnd);
        postIndex--;
        root.right=buildTreeMPChild(midOrder,postOrder,midIndex+1,midEnd);
        root.left=buildTreeMPChild(midOrder,postOrder,midBegin,midIndex-1);
        return root;


    }
    public  TreeNode buildTreeMP(char[] midOrder,char [] postOrder){
        postIndex=postOrder.length-1;
        return buildTreeMPChild(midOrder,postOrder,0,midOrder.length-1);
    }

    //根据二叉树创建一个字符串
    //给你一个二叉树的根结点，请你采用前序遍历的方式，将二叉树转换成为一个由括号和字符组成的字符串
    //空节点由一对括号表示，省略没有意义的括号
    //输入【1，2，3，4】输出：1（2（4））（3）
    //输入【1,2，3，null，4】输出：1（2（）（4））（3）
    private void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if (root==null){
            return;
        }
        stringBuilder.append(root.val);
        if (root.left!=null){
            stringBuilder.append('(');
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(')');
        }else//左边为空
            {
                //两边均为空
            if (root.right==null){
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        if (root.right!=null){
            stringBuilder.append('(');
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(')');
        }else {
            return;
        }
    }
    public String tree2str(TreeNode root){
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

}
